package Z.dailyExercise._0115;

import java.nio.file.ClosedWatchServiceException;

public class _面试题0803魔术索引 {

    /**
     * 题解：判断魔术索引就是寻找第一个index-num=0 的数字
     * 因为二分查找不方便寻找第一个数字 所以采用剪枝方法
     * 先递归左边的数字 如果存在 就直接返回 如果不存在再判断中间数
     * 有点类似于中旭遍历
     * @param nums
     * @return
     */
    public int findMagicIndex(int[] nums) {

       return helper(nums,0,nums.length-1);

    }
    /**
     * 判断当前区间是否有魔术索引
     *
     */

    public int helper(int[] nums,int low,int high){
        if (low > high){
            return -1;
        }
        int mid = low + (high-low)/2;

        int ans =helper(nums,low,mid-1) ;

        if (ans == -1){

            if (mid-nums[mid] == 0){
                return mid;
            }


        }else {
            return ans;
        }

        return helper(nums,mid+1,high);
    }

}
